package com.github.yangyishe.p100;

import java.sql.ResultSet;
import java.util.Stack;

/**
 * 71. 简化路径
 * https://leetcode.cn/problems/simplify-path/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。
 *
 * 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。
 *
 * 请注意，返回的 规范路径 必须遵循下述格式：
 *
 * 始终以斜杠 '/' 开头。
 * 两个目录名之间必须只有一个斜杠 '/' 。
 * 最后一个目录名（如果存在）不能 以 '/' 结尾。
 * 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
 * 返回简化后得到的 规范路径 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：path = "/home/"
 * 输出："/home"
 * 解释：注意，最后一个目录名后面没有斜杠。
 * 示例 2：
 *
 * 输入：path = "/../"
 * 输出："/"
 * 解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。
 * 示例 3：
 *
 * 输入：path = "/home//foo/"
 * 输出："/home/foo"
 * 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
 * 示例 4：
 *
 * 输入：path = "/a/./b/../../c/"
 * 输出："/c"
 *
 *
 * 提示：
 *
 * 1 <= path.length <= 3000
 * path 由英文字母，数字，'.'，'/' 或 '_' 组成。
 * path 是一个有效的 Unix 风格绝对路径。
 */
public class Problem71 {
    public static void main(String[] args) {
        String path="/a/./b/../../c/";

        Problem71 problem71 = new Problem71();
        String s = problem71.simplifyPath(path);
        System.out.println(s);
    }

    /**
     * 思路:
     * 此题的要求, 实际由若干个小要求构成的. 注: 以下要求描述从理解方面角度考虑, 不是真实的replace
     * 1. 出现`/./`的情况, 需要简化为`/`
     * 2. 出现`/../`的情况, 需要简化为向上一层结构. 如果没有上一层结构, 则使用根目录替代
     * 3. 出现`/////`的n个`/`情况, 视为一个`/`
     * 4. 路径最后出现的`/`, 消去.
     * 5. 其他方式, 都视为路径本身, 包括`/a./`,`/.../`. ps: 一个目录不可能包含`/`
     *
     * 此题使用栈比较容易实现.
     * 1. 一个目录栈, 保存从根目录出发的文件路径. 主要用来回溯上级目录之用.
     * 2. 语义解析部分, 可考虑使用快慢指针实现
     *  - 慢指针通常位置都在`/`上
     *  - 如果快指针遍历到`/`上, 且:
     *      - 快慢offset=1, 说明遇到了`//`的情况, 慢指针直接增加, 不产生新的语义
     *      - 快慢offset=2, 进而判断: 中间坐标的字符是否是`.`
     *          - 如果是, 表示语义: 当前文件. 不对目录栈产生影响, 慢指针重置
     *          - 如果不是, 表示语义: 深入目录. 目录栈增加.
     *      - 快慢offset=3, 进而判断: 中间对应两个坐标的字符是否均是`.`
     *          - 如果是, 表示语义: 返回上级陆慕. 目录栈在非空的情况pop
     *          - 如果不是, 表示语义: 深入目录. 目录栈增加
     *      - 快慢offset>3, 均表示: 深入目录. 目录栈增加
     * 3. 遍历到最后, 获取到最终目录栈, 分别将之逆序以`/`相隔, 保存到一个新的字符串中
     *
     * @param path
     * @return
     */
    public String simplifyPath(String path) {
        Stack<String> dirStack=new Stack<>();

        int slow=0;
        // 为了逻辑更简洁, 默认最后加一个`/`
        path=path+"/";
        for(int i=1;i<path.length();i++){
            char c=path.charAt(i);
            if(c=='/'){
                if(i-slow==1){
                    // do nothing
                }else if(i-slow==2&&path.charAt(i-1)=='.'){
                    // do nothing
                }else if(i-slow==3&&path.charAt(i-1)=='.'&&path.charAt(i-2)=='.'){
                    if (!dirStack.isEmpty()) {
                        dirStack.pop();
                    }
                }else{
                    dirStack.push(path.substring(slow+1,i));
                }
                slow=i;
            }
        }

        // 解释语义
        StringBuilder sb=new StringBuilder();
        for (String dir : dirStack) {
            sb.append("/").append(dir);
        }

        return sb.length()==0?"/":sb.toString();
    }
}
